Path Delay
Communication path delay measurements play an important role in the analysis, design and monitoring of networks. However, the clock skews (or frequency differences) between the clocks at the end points of the path can render the delay measurements inaccurate. To obtain more accurate delay measurements, the clock skews have to be accurately estimated and removed from (or compensated for) in the measurements.
End-to-end communication path delay traces are often used to analyze network performance. The measured path delays can be used to improve the design of networks, optimize the placement and use of network resources, monitor network loading and availability, optimize traffic routing and control mechanisms, detect network faults and traffic flow anomalies, etc. Delay traces are typically obtained by monitoring packet delays or by active probing. In either case, the difference between the arrival time of a packet (measured according to the destination clock), and its corresponding departure time from the source (indicated by a timestamp added by the source and conveyed by the packet), is considered to be the delay experienced by that packet.
If the source and destination clocks are perfectly synchronized, then the measured delay is the true delay between the two end points. However, in real systems, two clocks are rarely perfectly synchronized. The clocks can run at different speeds (i.e., have different frequencies). This difference in speed or frequency is called the clock skew. Given that the clocks at the end systems are not perfectly synchronized and run at different speeds, the delay measurements can be quite inaccurate. To obtain more accurate delay measurements, the clock skews have to be accurately estimated and removed from (or compensated for) in the measurements [1][2][3][4][5][6]. Network protocols such as the Network Time Protocol (NTP) and IEEE 1588 Precision Time Protocol (PTP) can be used for clock synchronization as well as perform network delay measurements.
Overview of IEEE 1588v2 PTP
The IEEE 1588v2 PTP defines a packet-based synchronization protocol for communicating frequency, phase and time-of-day information from a master to one or more slaves with sub-microsecond accuracy. PTP relies on the use of accurately timestamped packets (at nanosecond level granularity) sent from a master clock to one or more slave clocks to allow them to (frequency, phase or time) synchronize to the master clock. Synchronization information is distributed hierarchically, with a GrandMaster clock at the root of the hierarchy.
The GrandMaster provides the time reference for one or more slave devices. These slave devices can, in turn, act as master devices for further hierarchical layers of slave devices. PTP provides a mechanism (i.e., Best Master Clock Algorithm) for slave clocks to select the best master clock in their respective synchronization domain. The selection is performed according to the PTP attributes of the GrandMaster (e.g. PTP priority, clock class).
The PTP message exchange process (i.e., the PTP Delay Request/Delay Response flow) between a master and a slave is illustrated in FIG. 1. IEEE 1588 PTP allows for two different types of timestamping methods, either one-step or two-step. One-step clocks update time information within event messages (Sync and Delay-Req) on-the-fly, while two-step clocks convey the precise timestamps of packets in general messages (Follow_Up and Delay-Resp). A Sync message is transmitted by a master to its slaves and either contains the exact time of its transmission or is followed by a Follow_Up message containing this time. In a two-step ordinary or boundary clock, the Follow_Up message communicates the value of the departure timestamp for a particular Sync message.
FIG. 1 illustrates the basic pattern of synchronization message exchanges for the two-step clocks. The master 1 sends a Sync message to the slave 3 over the intervening packet network 2 and notes the time T1 at which it was sent. The slave 3 receives the Sync message and notes the time of reception T2. The master 1 conveys to the slave 3 the timestamp T1 by one of two ways: 1) Embedding the timestamp T1 in the Sync message. This requires some sort of hardware processing (i.e., hardware timestamping) for highest accuracy and precision (this is the one-step method) or 2) embedding the timestamp T1 in a Follow_Up message (as in the two-step method illustrated in FIG. 1). Next, the slave 3 sends a Delay_Req message to the master 1 and notes the time T3 at which it was sent according to the local clock 5 in the slave. The master 1 receives the Delay_Req message and notes the time of reception T4 according to the master clock 4. The master 1 conveys the timestamp T4 to the slave 3 by embedding it in a Delay_Resp message.
At the end of this exchange of PTP messages, the slave possesses all four timestamps {T1, T2, T3, T4}. These timestamps may be used to compute the clock skew and offset of the slave's clock with respect to the master and the communication delay of messages between the two clocks. The computation of offset often assumes that the master-to-slave and slave-to-master path delays are equal, i.e. a symmetrical communication path. Clock frequencies change over time, so periodic message exchanges are required. Because these clock variations change slowly, the period between message exchanges is typically on the order of milliseconds to seconds.
A clock with a non-zero skew will either run faster or slower than one with a zero skew. Using such a non-zero skew clock will certainly overestimate or underestimate the delay measurement of packet arrival, an important measure critical for optimal network operation. A number of existing techniques has been proposed to estimate the clock skew to remove its negative influence in the measured delay. Some components of these solutions such as the use of convex hull, linear programming, and definitions of objective functions are useful for estimating both skew and offset of clock.
Zhang et al. [4] use a convex hull algorithm to sort out relevant delay data and use three objective functions to determine which section of the convex hull that contains the optimal solution. In two dimensions, such algorithm can be viewed as creating an upper and a lower boundary of a convex polygon. For skew estimation, only the lower boundary is relevant. Thus, the convex hull algorithm processes the original collection of delay measurement into piecewise linear skew line segments while filtering out most of the delay measurement data.
The paper considers three different clock adjustment scenarios consisting of no clock reset, clock velocity adjustment, and instantaneous clock reset, the latter two of which can be considered as some form of clock reset. When there is no clock reset, there is only one convex hull to deal with. Otherwise the clock resets partition the delay data set into subsets, from each of which a distinct convex hull is formed.
For no clock reset, the clock skew is assumed to be constant. The paper also assumes that, for the instantaneous clock reset scenario, the clock skew is the same among all subsets of delay data, whilst, for clock velocity adjustment scenario, the clock skew changes over time. The points of clock resets are either given or assumed to be obtainable through analyzing the delay data set.
When there is no clock reset, the location where the optimal clock skew is easily obtained based on the conditions determined by some objective functions which are set out in the paper. Assuming the point of clocks resets are given, the paper identifies the section of the convex hull for the instantaneous clock reset scenario. Corresponding details for the clock velocity adjustment scenario according to the different objective functions are not provided.
In summary, the proposed solutions in Zhang et al are intended to estimate and remove the relative clock skew from delay measurements. The authors consider various clock reset scenarios with different assumptions of the skew characteristics. Three objective functions are proposed and underlying all these solutions is the use of convex hull to sort out relevant delay data on which candidate skew values are estimated.
Even if the clock resets can be found as proposed in this paper, usually they could be determined only after sufficient amount of data is collected (meaning the technique can only be used offline and not online as data is received). The presence of clock resets complicates clock estimation solutions. Therefore some form of data windowing may be needed.
Bletsas [6] presents the evaluation of three algorithms for estimating local clock parameters when the Internet is used to connect to a single time reference server. Kalman filtering is chosen for its optimality for the Gaussian data case and appealing recursive nature; the linear programming technique for its intuitive structure; and the averaging technique (referred as averaged time differences (ATD)) for its simplicity and wide spread deployment.
The performance of the algorithms depends on the delay behaviour of the NTP messages. If it is Gaussian, Kalman filtering technique is optimal. This technique also performs well with self-similar delay data when more delay data are available.
The linear prediction (LP) technique performs best compared to the other two techniques for the case of bursty traffic but not as well for completely independent traffic. This technique is a line-fitting technique that exploits both the forward and reverse path timestamps, by estimating a clock line that minimizes the distance between the line and the data
The averaged time differences (ATD), though inferior to LP and Kalman filtering techniques at the self-similar case, is simple and produces reasonable results for small number of measurements and when cost and accuracy trade-off cannot be avoided.
In summary, all algorithms in this document improve with increasing number of samples.
Moon et al. [2] disclose a linear programming technique to estimate skew with the objective of removing the skew inadvertent contribution from the delay measurement.
The goal of the skew estimation algorithm described here is to remove skew from measured network delays so as to make it consistent with the reference clock. As such, the model is tightly integrated to remove skew contribution in the measured delay.
Call Handover Process
The call handover process is of major importance within any mobile network. Fundamentally, it is necessary to ensure that it can be performed reliably and without disruption to any calls. Unreliable call handover can result in dropped calls, and this is one of the key factors that can lead to customer dissatisfaction, which in turn may lead to them changing to another mobile network provider. Accordingly handover is one of the key performance indicators monitored so that a robust cellular handover regime is maintained on the mobile network.
In handover between the radio access systems, handover preparation is done before changing systems, including tasks such as securing resources on the target radio access system, through cooperation between the radio access systems.
The mobile device sends a radio quality report containing the handover candidate base-stations and other information to the base station. The base station decides whether handover shall be performed based on the information in the report, identifies the base station and radio controller to switch to, and begins handover preparation.
Presently, the quality report does not include the synchronization accuracy of the candidate base stations which means that even if those base stations are not properly synchronized handover can still take place resulting in dropped calls and interrupted communication.
An object of the present invention is to provide simple but effective techniques for estimating frequency synchronization accuracy between a slave clock and a master clock.
A further object of the present invention is to provide for improved call handover for a mobile device between base stations in a mobile telephone network. Specifically, an object of the present invention is to improve the reliability of the handover process.